package LeetCode刷题.暑假刷的算法;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-08-24 16:10
 * @description: Functions of this class is 找出数组中出现了奇数次的数
 **/
public class 出现了奇数次的数 {
    public static void main(String[] args) {
        int nums[] = {1, 1, 2, 2, 3, 4, 4, 7, 6, 6,};
        getOddNum(nums);
    }

    /**
     * 异或法！！！！重要*********
     */
    private static void getOddNum(int nums[]) {
        int ans = 0;//根据相同的元素异或可以抵消，所有最后异或得出的结果就是那两个缺失的元素的异或结果
        for (int i : nums) {
            ans ^= i;
        }
        System.out.println(ans);
        //又因为两个元素是不同的，所以为了区分这两个元素，所以根据二进制数字来找，由于0^1=1可以区别两个数字，一个为1，一个为0，
        //所以找到两个元素异或结果最近的一位二进制数==1的那一位
        int position = 0;//用于标记具体哪一位为1
        for (int i = ans; (i & 1) == 0; i >>= 1) {//即当找到那一位为1的时候，即退出循环
            position++;
        }
        //然后通过position来讲所有元素分成两份，以此来找到其中一个数字
        int a = ans;//然后将两个元素相异或的结果，去所有元素中找到两个答案中的一个******
        for (int i = 0; i < nums.length; i++) {
            if (((nums[i] >> position) & 1) == 1) {//找到出所有元素该位置为1的
                //这里面肯定包含答案中的其中一个数字且肯定不包含另外一个数字
                a ^= nums[i];
            }
        }
        System.out.println(a + "," + (ans ^ a));
    }
}